package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.StackProblem;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 先序后序还原树 啊啊啊啊, 这个栈的方法, 怎么总想不到.
 *
 * @author tzp
 * @since 2020/9/11
 */
public class LC889_1 implements TreeProblem, StackProblem {

    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 5, 3, 6, 7};
        int[] post = {4, 5, 2, 6, 7, 3, 1};
        TreeNode treeNode = new LC889_1().constructFromPrePost(pre, post);
        System.out.println(treeNode);
    }

    public TreeNode constructFromPrePost(int[] pre, int[] post) {
        if (pre == null || pre.length == 0 || post == null || post.length == 0) {
            return null;
        }
        Deque<TreeNode> queue = new ArrayDeque<>();
        TreeNode root = new TreeNode(pre[0]);
        queue.addFirst(root);

        int i = 1, j = 0;
        while ((i < pre.length || j < pre.length) && queue.size() > 0) {
            if (queue.getFirst().val != post[j]) {
                queue.addFirst(new TreeNode(pre[i]));
                i++;
            } else {
                TreeNode child = queue.pop();
                TreeNode parent = queue.peekFirst();
                if (parent != null) {
                    if (parent.left == null) {
                        parent.left = child;
                    } else {
                        parent.right = child;
                    }
                }
                j++;
            }
        }
        return root;
    }
}
